Date: Thu, 07 Nov 1996 19:06:49 GMT
Server: NCSA/1.5
Content-type: text/html
Last-modified: Fri, 09 Aug 1996 22:47:40 GMT
Content-length: 2451

<HTML>
<HEAD>
<TITLE> Home Page of Eric Bach </TITLE>
</HEAD>

<BODY>

<H1> <!WA0><IMG ALIGN=MIDDLE SRC="http://www.cs.wisc.edu/~pubs/faculty-info/bach.gif">
 Eric Bach </H1>

<BLOCKQUOTE>
 Professor <BR>
 <BR>
 Computer Sciences Department <BR>
 University of Wisconsin <BR>
 1210 W. Dayton St. <BR>
 Madison, WI 53706-1685 <BR>
 <BR>
 telephone: (608) 262-1204 <BR>
 fax: (608) 262-9777 <BR>
 email: <!WA1><A HREF="mailto:bach@cs.wisc.edu">
 bach@cs.wisc.edu</A> <BR>
</BLOCKQUOTE>

<EM>Ph.D., University of California, Berkeley, 1984</EM> <BR>
<EM>Interests:</EM>
Theoretical computer science, computational number theory, algebraic
algorithms, complexity theory, cryptography, six-string automata
<P>

<HR>

<H2> Research Summary </H2>

I am interested in how one uses computers to efficiently solve
algebraic and number-theoretic problems (example: how does one
tell if a 100-digit number is prime without examining all possible
factors?). These problems have intrinsic mathematical interest,
as well as applications to random number generation, codes for
reliable and secure information transmission, computer algebra,
and other areas. <P>

I am also interested in applying probability theory to the design
and analysis of algorithms. For example, if a large number is
composite, it can be proved so by a simple test that uses an auxiliary
number, called a `witness.' In practice one usually finds a witness
by direct search among the small primes. This leads to the following
natural question. How large is the least witness, as a function
of the number tested? In recent work, we have given an accurate
heuristic model, based on probabilistic assumptions, that allows
this, and similar questions, to be answered. <P>

<H2> Recent Publications 
</H2>

Improved approximations for Euler products,
<EM>Proc. CNTA-4 (Canadian Math. Soc. Proceedings, v. 15) </EM>, 1995. <P>
 
DNA models and algorithms for NP-complete problems (with A. Condon,
E. Glaser, S. Tanguay),
<EM>Proc. 11th Annual Conf. on Computational Complexity</EM>, 1996. <P>
 
<EM>Algorithmic Number Theory (Volume I: Efficient Algorithms)</EM>
(with J. Shallit), MIT Press, 1996.  For info click on
<!WA2><A HREF="http://math.uwaterloo.ca/~shallit/ant.html" > 
ANT-1</A>.
<P>

<H2> <!WA3><A HREF="http://www.cs.wisc.edu/~bach/eric.ps" >
Curriculum Vitae </A>
</H2>
 
<HR>
<ADDRESS>
 This page created July 30, 1996.<BR>
 Email <!WA4><A HREF="mailto:bach@cs.wisc.edu">bach@cs.wisc.edu</A>
to report errors.
</ADDRESS>
<HR>

</BODY>
</HTML>

